<!DOCTYPE html>
<html lang=zh>
<head>
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
    <meta name="description" content="问题定义给定数组arr，长度T，其中某些arr[i]到arr[j]存在转移概率，将arr分成k组，使得arr的整体分组和最大。对于arr的每一个子数组arr[i..j]，其分组值定义为 arr[i]到arr[j]的转移概率arr的分组和是其每一个子数组的分组值之和 问题求解正向定义定义数据g[i]为arr[0..i]的最大分组和在g[j], 0 &lt;&#x3D; j &lt; i已知的前提下，将 arr">
<meta property="og:type" content="article">
<meta property="og:title" content="基于词频的中文分词">
<meta property="og:url" content="https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/index.html">
<meta property="og:site_name" content="拿铁轮的自留地">
<meta property="og:description" content="问题定义给定数组arr，长度T，其中某些arr[i]到arr[j]存在转移概率，将arr分成k组，使得arr的整体分组和最大。对于arr的每一个子数组arr[i..j]，其分组值定义为 arr[i]到arr[j]的转移概率arr的分组和是其每一个子数组的分组值之和 问题求解正向定义定义数据g[i]为arr[0..i]的最大分组和在g[j], 0 &lt;&#x3D; j &lt; i已知的前提下，将 arr">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-09-14T02:53:44.000Z">
<meta property="article:modified_time" content="2022-09-15T05:14:09.227Z">
<meta property="article:author" content="拿铁轮">
<meta name="twitter:card" content="summary">
    
    
      
        
          <link rel="shortcut icon" href="/images/favicon.ico">
        
      
      
        
          <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
        
      
      
        
          <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
        
      
    
    <!-- title -->
    <title>基于词频的中文分词</title>
    <!-- styles -->
    
<link rel="stylesheet" href="/css/style.css">

    <!-- persian styles -->
    
    <!-- rss -->
    
    
      <link rel="alternate" href="/true" title="拿铁轮的自留地" type="application/atom+xml" />
    
	<!-- mathjax -->
	
<meta name="generator" content="Hexo 4.2.1"><!-- hexo-inject:begin --><!-- hexo-inject:end --></head>

<body class="max-width mx-auto px3 ltr">
    
      <!-- hexo-inject:begin --><!-- hexo-inject:end --><div id="header-post">
  <a id="menu-icon" href="#" aria-label="目录"><i class="fas fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#" aria-label="目录"><i class="fas fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" aria-label="顶部" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fas fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        
        <li><a class="icon" aria-label="下一篇" href="/2021/03/28/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BF%AD%E4%BB%A3%E5%99%A8/"><i class="fas fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" aria-label="返回顶部" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" aria-label="分享文章" href="#"><i class="fas fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">上一篇</span>
      <span id="i-next" class="info" style="display:none;">下一篇</span>
      <span id="i-top" class="info" style="display:none;">返回顶部</span>
      <span id="i-share" class="info" style="display:none;">分享文章</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/" target="_blank" rel="noopener"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&text=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://service.weibo.com/share/share.php?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-weibo " aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&is_video=false&description=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li> -->
  <li><a class="icon" href="mailto:?subject=基于词频的中文分词&body=Check out this article: https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/"><i class="fas fa-envelope " aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://getpocket.com/save?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&name=基于词频的中文分词&description=" target="_blank" rel="noopener"><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://news.ycombinator.com/submitlink?u=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&t=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li> -->
</ul>



    </div>
    <div id="toc">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#问题定义"><span class="toc-number">1.</span> <span class="toc-text">问题定义</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#问题求解"><span class="toc-number">2.</span> <span class="toc-text">问题求解</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#正向定义"><span class="toc-number">2.1.</span> <span class="toc-text">正向定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#反向定义"><span class="toc-number">2.2.</span> <span class="toc-text">反向定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#说明"><span class="toc-number">2.3.</span> <span class="toc-text">说明</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#代码实现"><span class="toc-number">3.</span> <span class="toc-text">代码实现</span></a></li></ol>
    </div>
  </span>
</div>

    
    <div class="content index py4">
        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle" itemprop="name headline">
        基于词频的中文分词
    </h1>



    <div class="meta">
      <span class="author" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span itemprop="name">拿铁轮</span>
      </span>
      
    <div class="postdate">
      
        <time datetime="2022-09-14T02:53:44.000Z" itemprop="datePublished">2022-09-14</time>
        
      
    </div>


      

      

    </div>
  </header>
  

  <div class="content" itemprop="articleBody">
    <h2 id="问题定义"><a href="#问题定义" class="headerlink" title="问题定义"></a>问题定义</h2><p>给定数组arr，长度T，其中某些arr[i]到arr[j]存在转移概率，将arr分成k组，使得arr的整体分组和最大。<br>对于arr的每一个子数组arr[i..j]，其分组值定义为 arr[i]到arr[j]的转移概率<br>arr的分组和是其每一个子数组的分组值之和</p>
<h2 id="问题求解"><a href="#问题求解" class="headerlink" title="问题求解"></a>问题求解</h2><h3 id="正向定义"><a href="#正向定义" class="headerlink" title="正向定义"></a>正向定义</h3><p>定义数据g[i]为arr[0..i]的最大分组和<br>在g[j], 0 &lt;= j &lt; i已知的前提下，将 arr[j .. i] 分成一组，则g[i] = g[j] + trans[j, i] ，所以</p>
<script type="math/tex; mode=display">g[i] = max(g[j] + trans(j, i)), 0 <= j < i</script><p>g[T - 1]即为所求。</p>
<h3 id="反向定义"><a href="#反向定义" class="headerlink" title="反向定义"></a>反向定义</h3><p>定义数据g[i]为arr[i..T-1]的最大分组和，其余定义与正向定义类似</p>
<h3 id="说明"><a href="#说明" class="headerlink" title="说明"></a>说明</h3><p>jieba/<strong>init</strong>.py中的Tokenizer.calc与wordseg/ViterbiCWS.py中的ViterbiSearch的实现是等价的，均可实现序列的最大分组，不同点在于</p>
<ol>
<li>DAG的定义不同<br>如对于句子”学生会主动完成作业”，<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">&#123;<span class="number">0</span>: [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>], <span class="number">1</span>: [<span class="number">1</span>], <span class="number">2</span>: [<span class="number">2</span>, <span class="number">3</span>], <span class="number">3</span>: [<span class="number">3</span>, <span class="number">4</span>], <span class="number">4</span>: [<span class="number">4</span>], <span class="number">5</span>: [<span class="number">5</span>, <span class="number">6</span>], <span class="number">6</span>: [<span class="number">6</span>], <span class="number">7</span>: [<span class="number">7</span>, <span class="number">8</span>], <span class="number">8</span>: [<span class="number">8</span>]&#125;  <span class="comment"># jieba</span></span><br><span class="line">&#123;<span class="number">0</span>: [<span class="number">0</span>], <span class="number">1</span>: [<span class="number">0</span>, <span class="number">1</span>], <span class="number">2</span>: [<span class="number">0</span>, <span class="number">2</span>], <span class="number">3</span>: [<span class="number">3</span>], <span class="number">4</span>: [<span class="number">3</span>, <span class="number">4</span>], <span class="number">5</span>: [<span class="number">5</span>], <span class="number">6</span>: [<span class="number">5</span>, <span class="number">6</span>], <span class="number">7</span>: [<span class="number">7</span>], <span class="number">8</span>: [<span class="number">7</span>, <span class="number">8</span>]&#125;  <span class="comment"># ViterbiSearch</span></span><br></pre></td></tr></table></figure></li>
<li>用于实现DP的状态定义不同<br>jieba使用的正向定义，ViterbiSearch使用的是反向定义</li>
</ol>
<h2 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h2><p>使用反向定义，实现逻辑与ViterbiSearch一致。<br>可以尝试提升“学生会”的词频，使得cut能且分出“学生会”。<br>或者提升 长江大桥 的词频，使得cut能切分出 “长江大桥”</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line">freq = &#123;</span><br><span class="line">    <span class="string">"学生"</span>: <span class="number">400</span>,</span><br><span class="line">    <span class="string">"学生会"</span>: <span class="number">20</span>,</span><br><span class="line">    <span class="string">"完成"</span>: <span class="number">500</span>,</span><br><span class="line">    <span class="string">"作业"</span>: <span class="number">300</span>,</span><br><span class="line">    <span class="string">"主动"</span>: <span class="number">400</span>,</span><br><span class="line">    <span class="string">"学"</span>: <span class="number">10</span>,</span><br><span class="line">    <span class="string">"生"</span>: <span class="number">10</span>,</span><br><span class="line">    <span class="string">"会"</span>: <span class="number">20</span>,</span><br><span class="line">    <span class="string">"主"</span>: <span class="number">50</span>,</span><br><span class="line">    <span class="string">"动"</span>: <span class="number">10</span>,</span><br><span class="line">    <span class="string">"完"</span>: <span class="number">100</span>,</span><br><span class="line">    <span class="string">"成"</span>: <span class="number">55</span>,</span><br><span class="line">    <span class="string">"作"</span>: <span class="number">40</span>,</span><br><span class="line">    <span class="string">"业"</span>: <span class="number">5</span>,</span><br><span class="line">    <span class="string">"大桥"</span>: <span class="number">20</span>,</span><br><span class="line">    <span class="string">"南京"</span>: <span class="number">60</span>,</span><br><span class="line">    <span class="string">"南京市"</span>: <span class="number">30</span>,</span><br><span class="line">    <span class="string">"市长"</span>: <span class="number">40</span>,</span><br><span class="line">    <span class="string">"江大桥"</span>: <span class="number">888</span>,</span><br><span class="line">    <span class="string">"长江大桥"</span>: <span class="number">666</span>,</span><br><span class="line">    <span class="string">"南"</span>: <span class="number">10</span>,</span><br><span class="line">    <span class="string">"京"</span>: <span class="number">40</span>,</span><br><span class="line">    <span class="string">"市"</span>: <span class="number">6</span>,</span><br><span class="line">    <span class="string">"长"</span>: <span class="number">7</span>,</span><br><span class="line">    <span class="string">"江"</span>: <span class="number">50</span>,</span><br><span class="line">    <span class="string">"大"</span>: <span class="number">5</span>,</span><br><span class="line">    <span class="string">"桥"</span>: <span class="number">40</span>,</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">total = <span class="number">3000</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">build_dag</span><span class="params">(sentence: str)</span> -&gt; dict:</span></span><br><span class="line">    <span class="string">"""</span></span><br><span class="line"><span class="string">    构建以每个token结尾的有向词图</span></span><br><span class="line"><span class="string">    如 "学生会主动完成作业" =&gt; &#123;0: [0], 1: [0, 1], 2: [0, 2], 3: [3], 4: [3, 4], 5: [5], 6: [5, 6], 7: [7], 8: [7, 8]&#125;</span></span><br><span class="line"><span class="string">    :param sentence:</span></span><br><span class="line"><span class="string">    :return:</span></span><br><span class="line"><span class="string">    """</span></span><br><span class="line">    n = len(sentence)</span><br><span class="line">    dag = &#123;</span><br><span class="line">        i: [j <span class="keyword">for</span> j <span class="keyword">in</span> range(i + <span class="number">1</span>) <span class="keyword">if</span> freq.get(sentence[j:i + <span class="number">1</span>], <span class="number">0</span>)]</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(n)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dag</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">route</span><span class="params">(sentence: str, dag: dict)</span>:</span></span><br><span class="line">    <span class="string">"""</span></span><br><span class="line"><span class="string">    g[i] = (prob, j)，prob为sentence[0..i]的最大分组和，j为sentence[i]所属的分组起始位置</span></span><br><span class="line"><span class="string">    g[i].prob = max(g[j] + trans(j, i)), 0 &lt;= j &lt; i</span></span><br><span class="line"><span class="string">    g[i].j = argmax max(g[j] + trans(j, i)), 0 &lt;= j &lt; i</span></span><br><span class="line"><span class="string">    :param sentence:</span></span><br><span class="line"><span class="string">    :param dag:</span></span><br><span class="line"><span class="string">    :return:</span></span><br><span class="line"><span class="string">    """</span></span><br><span class="line">    n = len(sentence)</span><br><span class="line">    g = &#123;<span class="number">-1</span>: (<span class="number">0</span>, <span class="number">0</span>)&#125;</span><br><span class="line">    logtotal = math.log(total)</span><br><span class="line">    <span class="keyword">for</span> idx <span class="keyword">in</span> range(n):</span><br><span class="line">        g[idx] = max(</span><br><span class="line">            (</span><br><span class="line">                g[idx - <span class="number">1</span>][<span class="number">0</span>] + math.log(freq.get(sentence[x: idx + <span class="number">1</span>]) <span class="keyword">or</span> <span class="number">1</span>) - logtotal,</span><br><span class="line">                x</span><br><span class="line">            )</span><br><span class="line">            <span class="keyword">for</span> x <span class="keyword">in</span> dag[idx]</span><br><span class="line">        )</span><br><span class="line">    <span class="keyword">return</span> g</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">cut</span><span class="params">(sentence: str)</span>:</span></span><br><span class="line">    dag = build_dag(sentence)</span><br><span class="line">    g = route(sentence, dag)</span><br><span class="line"></span><br><span class="line">    n = len(sentence)</span><br><span class="line">    segments = deque()</span><br><span class="line">    idx = n - <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> idx &gt;= <span class="number">0</span>:</span><br><span class="line">        prev = g[idx][<span class="number">1</span>]</span><br><span class="line">        segments.appendleft(sentence[prev: idx + <span class="number">1</span>])</span><br><span class="line">        idx = prev - <span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> segments</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    sents = [</span><br><span class="line">        <span class="string">"学生会主动完成作业"</span>,</span><br><span class="line">        <span class="string">"南京市长江大桥"</span></span><br><span class="line">    ]</span><br><span class="line">    <span class="keyword">for</span> sent <span class="keyword">in</span> sents:</span><br><span class="line">        print(<span class="string">"%s =&gt; %s"</span> % (sent, <span class="string">"/"</span>.join(cut(sent))))</span><br><span class="line">    <span class="comment"># 学生会主动完成作业 =&gt; 学生/会/主动/完成/作业</span></span><br><span class="line">    <span class="comment"># 南京市长江大桥 =&gt; 南京/市长/江大桥</span></span><br></pre></td></tr></table></figure>
  </div>
</article>

    <div class="blog-post-comments">
        <div id="disqus_thread">
            <noscript>加载评论需要在浏览器启用 JavaScript 脚本支持。</noscript>
        </div>
    </div>



        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/about/">关于</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/categories/">分类</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/search/">搜索</a></li>
        
      </ul>
    </div>

    <div id="toc-footer" style="display: none">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#问题定义"><span class="toc-number">1.</span> <span class="toc-text">问题定义</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#问题求解"><span class="toc-number">2.</span> <span class="toc-text">问题求解</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#正向定义"><span class="toc-number">2.1.</span> <span class="toc-text">正向定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#反向定义"><span class="toc-number">2.2.</span> <span class="toc-text">反向定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#说明"><span class="toc-number">2.3.</span> <span class="toc-text">说明</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#代码实现"><span class="toc-number">3.</span> <span class="toc-text">代码实现</span></a></li></ol>
    </div>

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/" target="_blank" rel="noopener"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&text=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://service.weibo.com/share/share.php?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-weibo fa-lg" aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&is_video=false&description=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li> -->
  <li><a class="icon" href="mailto:?subject=基于词频的中文分词&body=Check out this article: https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/"><i class="fas fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://getpocket.com/save?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&title=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&name=基于词频的中文分词&description=" target="_blank" rel="noopener"><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://news.ycombinator.com/submitlink?u=https://hillbamboo.gitee.io/2022/09/14/%E5%9F%BA%E4%BA%8E%E8%AF%8D%E9%A2%91%E7%9A%84%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D/&t=基于词频的中文分词" target="_blank" rel="noopener"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li> -->
</ul>



    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fas fa-bars fa-lg" aria-hidden="true"></i> 菜单</a>
        <a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fas fa-list fa-lg" aria-hidden="true"></i> 目录</a>
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fas fa-share-alt fa-lg" aria-hidden="true"></i> 分享</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up fa-lg" aria-hidden="true"></i> 返回顶部</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy;
    
    
    2017-2022
    拿铁轮
  </div>
  <div class="footer-right">
    <nav>
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </nav>
  </div>
</footer>

    </div>
    <!-- styles -->



  <link rel="preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.2/css/all.min.css" crossorigin="anonymous" onload="this.onload=null;this.rel='stylesheet'"/>


    <!-- jquery -->
 
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" crossorigin="anonymous"></script> 




<!-- clipboard -->

  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.7/clipboard.min.js" crossorigin="anonymous"></script> 
  
  <script type="text/javascript">
  $(function() {
    // copy-btn HTML
    var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"复制到粘贴板！\">";
    btn += '<i class="far fa-clone"></i>';
    btn += '</span>'; 
    // mount it!
    $(".highlight table").before(btn);
    var clip = new ClipboardJS('.btn-copy', {
      text: function(trigger) {
        return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
      }
    });
    clip.on('success', function(e) {
      e.trigger.setAttribute('aria-label', "复制成功！");
      e.clearSelection();
    })
  })
  </script>


<script src="/js/main.js"></script>

<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

<!-- Cloudflare Analytics -->

<!-- Umami Analytics -->

<!-- Disqus Comments -->

    <script type="text/javascript">
        var disqus_shortname = 'cactus-1';

        (function(){
            var dsq = document.createElement('script');
            dsq.type = 'text/javascript';
            dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        }());
    </script>

<!-- utterances Comments --><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->

</body>
</html>
